// 记忆化搜索，保存重叠子问题的结果，不再计算
package main

import "fmt"

func main() {
	v := fib(1000)
	fmt.Println(v)
}

var data = make(map[int]int)

func fib(n int) int {
	if n <= 2 {
		return 1
	}

	// 保存计算的子问题
	if v, ok := data[n]; ok {
		return v
	}

	v := fib(n-1) + fib(n-2)
	data[n] = v // 保存计算子问题的结果
	return v
}
